package airthmetic.exercise.dp;

import java.util.Arrays;

public class _300_最长递增子序列 {
    public int lengthOfLIS(int[] nums) {
        /*
         动态规划思考问题

         1.确定状态参数/选择
           状态参数:在子问题与原问题之间变化的值  此题为nums的index
           选择/决策： 做选择使状态参数变化并趋近于原问题   此题为循环中nums的当前index值, 对比 比当前index小的最长子序列，选择更长的递增子序列

         2.定义dp数组(dp table)的含义： nums[i]的最长子序列长度 即dp[i]的值
         3.初始化状态参数: 此题初始化长度都为1
         4.确定状态转移逻辑 （状态转移公式） 怎么根据子问题推求解原问题
           在这一步动态规划的思想史:通过子问题的解推导原问题的解
           也就是说： 如果你已经计算出dp[0],dp[1]... dp[i-2], dp[i-1]的值之后，你如何计算出dp[i]的值
           当然这个过程我们通过组选择来让状态转移的
           状态转移公式：
           dp[i] = Math.max(dp[i], dp[j] + 1)
        */
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);

        int max = 0;
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }


    public int lengthOfLIS2(int[] nums) {
        /*
        1.确定状态参数与选择决策
            状态参数：状态参数是在子问题与原问题之间变化的值
            此题为nums的下标,即外层循环的子问题数组的长度
            选择/决策：做选择使状态参数不断变化，并趋近于原问题的解

        2.定义dp table
            dp表,动态规划的思想是根据子问题推导原问题。子问题需要缓存，被原问	  题求解时使用。
            此题dp table的定义为：nums[i]下标对应字符串，能找到的最长递增子	   序列长度即dp[i]的值。

        3.初始化dp table
            根据题意单个元素也是有长度，长度为1。所以可以初始化所有dp[i]长度		为1。

        4.推导状态转移公式
            动态规划的思想是，根据子问题推导原问题。
            即得知dp[0],dp[1],dp[i-2],dp[-1]之后如何推导出dp[i]的值
            此题根据题意，如果内层循环小于外层循环的值。此时递增子序列长度应该	 +1。就是拼上外层循环 `状态参数`。

            for(int i=0; i< nums.length; i++){
                for(int j=0; j<i; j++){
                    if(nums[i] > nums[j]){
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
            }

        */

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }

            max = Math.max(dp[i], max);
        }
        return max;

    }

    public int lengthOfLIS3(int[] nums) {
        /**
         动态规划思想解决问题
         因为此题具备重叠子问题和无后效性以及最优子结构所以可以用动态规划思想解决问题
         1.确定状态参数和选择
         这里思考可以将 [0,1,0,3,2] 看成 [0,1,0,3,2,3] 的子问题
         状态参数：状态参数是子问题与原问题之间不断变化的值
         此题的状态参数是下标 i
         选择/决策：做选择使状态参数不断变化并趋近于原问题的解
         此题的选择是nums[i] nums[j]  选择不同的下标组成的子序列

         2. 定义dp table的含义
         动态规划的思想是根据子问题的解推导原问题
         int[] dp = new int[nums.length + 1];
         此题dp table的含义是 dp[i]是nums[0]~nums[i] 的最长递增子序列长度

         3. 初始化dp table
         此题dp[i]为1，因为一个元素自己也是特殊的递增子序列所以都为1


         4. 推导状态转移公式
         动态规划的思想是根据子问题的解推导原问题
         即我们得知dp[0]...d[1]...dp[i-2]...dp[i-1]的解之后怎么推导出dp[i]的值
         for(int i=0; i<nums.length; i++){
         for(int j=0; j<i; j++){
         if(i < j){
         dp[i] = Math.max(dp[i], dp[j] + 1);
         }
         }
         }
         */

        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int max = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    max = Math.max(max,dp[i]);
                }
            }
        }

        return max;



    }

    // 普通动态规划
    public static int lengthOfLIS4(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        for(int i=0; i<nums.length; i++){
            dp[i][i] = 1;
        }

        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[j] > nums[i]){
                    dp[i][j] = dp[i][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }

        return dp[0][nums.length-1];

    }


    // 状态压缩动态规划
    // 根据题意，求解dp[i][j] 只用到dp[i][j-1] dp[i-1][j] dp[i-1][j-1] 所以压缩二维数组为一维数组
    // 准备leftUp 变量  表示是当前dp[j](dp[i][j]) 左上角的数，相当于dp[i−1][j−1],初始化的时候为0
    // 准备up 变量 表示是当前dp[j](dp[i][j]) 正上方的数，相当于dp[i−1][j],初始化的时候为0
    // dp[j-1] 表示dp[j](dp[i][j])左边的数据，相当于dp[i][j−1]
    // 每一轮结束后，leftUp的值都向前滚动一个，变成正上方的数，也就是up
    public int longestCommonSubsequence(String text1, String text2) {
        /**
         因为问题具备重叠子问题和无后效性以及最优子结构。 动态规划！
         重叠子问题：t1[i] t2[j] 被后续用到
         无后效性： t1[i] t2[j] 不会被后续的选择影响
         最优子结构：t1[i] t2[j] 可以被后续问题使用

         动态规划思想：
         1.确定状态参数和选择
         先思考什么是原问题 什么是子问题
         原问题： t1[i] t2[j]
         子问题： t1[i-1] t2[j-1]

         状态参数： t1[i] t2[j]

         选择/决策： 做选择使状态参数不断变化并趋近于原问题的解
         选择不同的下标

         2.定义dp table含义
         int[][] dp = new int[t1.length+1][t2.length+1];
         dp[i][j] 表示t1[0~i]与t2[0~j]的两个字符串最长公共子序列长度

         3.初始化 dp table
         如果t1[0] 那么无论t2[j]为几个字符，最长公共子序列长度都是0
         如果t2[0] 那么无论t1[i]为几个字符，最长公共子序列长度都是0

         4.推导状态转移公式
         for(int i=0; i<t1.length; i++){
         for(int j=0; j<t2.length; j++){
         if(t1[i] == t2[j]){
         dp[i][j] = dp[i-1][j-1]+1;
         }else{
         dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
         }
         }
         }
         */
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();
        int n = t1.length;
        int m = t2.length;

        int[] dp = new int[m+1];
        int up = 0;
        for(int i=1; i<=n; i++){
            int leftUp = 0;
            for(int j=1; j<=m; j++){
                up = dp[j];
                if(t1[i-1] == t2[j-1]){
                    dp[j] = leftUp + 1;
                }else{
                    dp[j] = Math.max(dp[j-1], up);
                }
                leftUp =up;
            }
        }


        return dp[m];
    }

    // 状态压缩写法
    // 根据题意求解 dp[i][j] 只用到 dp[i][j-1] dp[i+1][j] dp[i+1][j-1]
    // 所以压缩成一维数组
    // 定义一个 leftDown 表示左下
    // 定义一个 down 表示下
    // 左直接用 dp[j-1]表示
    public int longestPalindromeSubseq4(String s) {
        /**
         因为问题具备重叠子问题和无后效性以及最优子结构。动态规划！
         重叠子问题： sc[i] sc[j] 是重叠子问题被后续使用
         无后效性：   sc[i] sc[j] 不会因为后续的选择而改变
         最优子结构： sc[1] sc[j] 具有独立性和最优性，可以被后续使用

         动态规划思考问题：
         1.确定状态参数和选择
         先思考什么是原问题 什么是子问题
         原问题：sc[i] sc[j]
         子问题: sc[i] sc[j-1] sc[i+1] sc[j]

         状态参数两个：i j 下标

         选择/决策：不断选择 i j下标

         2.定义dp table的含义
         int[][] dp = new int[s.length][s.length];
         dp[i][j]表示i开始j结束的字符串最长回文子序列长度

         3.初始化dp table
         单个字符也是特殊的回文子序列 所以单个字符都是1
         i>j不符合字符串的定义 所以是0

         4.推导状态转移公式
         for(int i=0; i<sc.length; i++){
         for(int j=i+1; j<sc.length; j++){
         if(sc[i] == sc[j]){
         dp[i][j] = dp[i+1][j-1] + 2;
         }else{
         dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
         }
         }
         }

         */
        char[] sc = s.toCharArray();
        int n = sc.length;
        int[] dp = new int[n];
        for(int i=n-1; i>=0; i--){
            dp[i] = 1;
            int leftDown = 0;
            for(int j=i+1; j<sc.length; j++){
                int down = dp[j];
                if(sc[i] == sc[j]){
                    dp[j] = leftDown + 2;
                }else{
                    dp[j] = Math.max(dp[j-1], dp[j]);
                }
                leftDown = down;
            }
        }

        return dp[n-1];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0,1,0,3,2,3};
        System.out.println(lengthOfLIS4(nums));
    }
}
